import java.util.Map;

/*
 * @lc app=leetcode.cn id=525 lang=java
 *
 * [525] 连续数组
 */

// @lc code=start
class Solution {
    /**
     * 把0当-1处理，那么sum[0~i] == sum[0~j]时，说明sum[i+1~j]==0,故j-i即数组长度。
     * 累加sum，如果map中无sum这个数值的key，放入sum和对应下标i。
     * 若有，则j-i为其长度，不需更新下标，保持下标的最低位置。
     */
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> mp = new HashMap<>();//k是sum程度， v是下标
        int sum = 0;
        int ans = 0;
        mp.put(0, -1);//一开始先放一个0，-1。防止只有数组为[0,1]时无法得到结果。
        for (int i=0 ;i<nums.length ;i++) {
            if(nums[i]==0) sum--;//当成-1处理
            else sum++;
            if(mp.containsKey(sum)){//有这个key，那么更新数组长度。
                ans = Math.max(ans,i-mp.get(sum));//j-i
            }else{
                mp.put(sum, i);
            }
        }
        return ans;
    }
}
// @lc code=end

